import java.util.*;

class Solution07 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 创建一个数组进行结果添加
        int[] ret = new int[numCourses];
        int index = 0;// 表示存储结点的位置
        // 创建哈希表
        Map<Integer, List<Integer>> hashMap = new HashMap<>();
        // 创建一个数组存储每个点的入度
        int[] in = new int[numCourses];
        // 根据哈希表建图
        int m = prerequisites.length;
        for (int i = 0; i < m; i++) {
            // 取出里面的元素
            int a = prerequisites[i][0], b = prerequisites[i][1];
            // 进行判断
            if (!hashMap.containsKey(b)) {
                hashMap.put(b, new ArrayList<>());
            }
            hashMap.get(b).add(a);
            // 入度加1
            // 起点的入度为0
            in[a]++;
        }
        // 创建队列
        Queue<Integer> q = new LinkedList<>();
        // 将入度为0的点添加到队列
        for (int i = 0; i < numCourses; i++) {
            // 进行判断
            if (in[i] == 0) {
                q.add(i);
            }
        }
        // 循环判断
        while (!q.isEmpty()) {
            // 取出队头元素
            int t = q.poll();
            ret[index++] = t;
            for (int x : hashMap.getOrDefault(t, new ArrayList<>())) {
                in[x]--;
                // 进行判断
                if (in[x] == 0) {
                    // 添加到队列
                    q.add(x);
                }
            }
        }
        // 判断是否有环
        if (index == numCourses) {
            return ret;
        }
        return new int[0];
    }
}